#include <iostream>
#include <vector>
#include <queue>

// BFS解决：Flood Fill算法
// 1.图像渲染
class Solution1
{
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
public:
    std::vector<std::vector<int>> floodFill(std::vector<std::vector<int>>& image, int sr, int sc, int color) 
    {
        // 0.准备阶段
        int len = image[0].size(), high = image.size();
        int flag = image[sr][sc]; // 记录初始像素点
        if(image[sr][sc] == color) return image;

        // 将所有满足要求的位置插入到队列中
        std::queue<std::pair<int,int>> pos;
        pos.emplace(sr, sc);
        image[sr][sc] = color;
        // 写法2：借助向量数组
        while(!pos.empty()){
            int x = pos.front().first, y = pos.front().second;
            pos.pop();
            for(int i=0; i<4; i++){
                int a = x + dx[i], b = y + dy[i];
                if(a >= 0 && a < high && b >=0 && b < len && image[a][b] == flag){
                    pos.emplace(a, b);
                    image[a][b] = color;
                }
            }
        }

        // 写法1：借助if多次判断
        //while(!pos.empty())
        //{
        //    int x = pos.front().first, y = pos.front().second;
        //    std::cout << x << ":" << y << std::endl;
        //    pos.pop();
        //    if(x - 1 >= 0 && image[x - 1][y] == flag){
        //        image[x-1][y] = color;
        //        pos.emplace(x-1, y);
        //    }
        //    if(x + 1 < high && image[x + 1][y] == flag){
        //        image[x+1][y] = color;
        //        pos.emplace(x+1, y);
        //    }
        //    if(y - 1 >= 0 && image[x][y - 1] == flag){
        //        image[x][y-1] = color;
        //        pos.emplace(x, y - 1);
        //    }
        //    if(y + 1 < len && image[x][y+1] == flag){
        //        image[x][y+1] = color;
        //        pos.emplace(x, y+1);
        //    }
        //}
        return image;
    }
};